جہت کی لعنت
جہت کی لعنت سے مراد مختلف مظاہر ہیں جو اعلی جہتی خالی جگہوں میں اعداد و شمار کا تجزیہ اور ترتیب دیتے وقت پیدا ہوتے ہیں جو کم جہتی ترتیبات میں نہیں ہوتے جیسے کہ روزمرہ کے تجربے کی سہ جہتی جسمانی جگہ۔ ڈائنامک پروگرامنگ میں مسائل پر غور کرتے وقت یہ اظہار رچرڈ ای بیل مین نے وضع کیا تھا۔[1][2]
جہتی طور پر ملعون مظاہر ساحہ میں پائے جاتے ہیں جیسے عددی تجزیہ، نمونے لینے، امتزاج، مشین آموزی، اعداد و شمار کا تجزیہ اور اعداد و شمار کا مجموعہ۔ ان مسائل کا عام موضوع یہ ہے کہ جب جہت بڑھ جاتی ہے تو خلا کا حجم اتنی تیزی سے بڑھ جاتا ہے کہ دستیاب اعداد و شمار ویرل ہو جاتا ہے۔ ایک قابل اعتماد نتیجہ حاصل کرنے کے لیے، اعداد و شمار کی ضرورت کی مقدار اکثر جہتی کے ساتھ تیزی سے بڑھتی ہے۔ اس کے علاوہ، اعداد و شمار کو منظم کرنا اور تلاش کرنا اکثر ایسے علاقوں کا پتہ لگانے پر انحصار کرتا ہے جہاں اشیاء ایک جیسی خصوصیات کے ساتھ گروپ بناتے ہیں۔ تاہم، اعلی جہتی اعداد و شمار میں، تمام اشیاء بہت سے طریقوں سے کم اور مختلف دکھائی دیتی ہیں، جو اعداد و شمار کی تنظیم کی مشترکہ حکمت عملیوں کو موثر ہونے سے روکتی ہے۔
ساحہ
[ترمیم]کچھ مسائل میں، ہر متغیر متعدد مجرد اقدار میں سے ایک لے سکتا ہے یا ممکنہ قدروں کی حد کو محدود تعداد میں امکانات دینے کے لیے تقسیم کیا جاتا ہے۔ متغیرات کو ایک ساتھ لے کر، قدروں کے امتزاج کی ایک بڑی تعداد پر غور کیا جانا چاہیے۔ اس اثر کو مشترکہ دھماکے کے نام سے بھی جانا جاتا ہے۔ یہاں تک کہ بائنری متغیرات کی سادہ ترین صورت میں، ممکنہ امتزاج کی تعداد پہلے سے ہی ہے، جہت میں کفایتی ہے۔ سادہ لوح، ہر اضافی جہت تمام مجموعوں کو آزمانے کے لیے درکار کوشش کو دگنا کر دیتی ہے۔
نمونے
[ترمیم]ریاضی کی جگہ میں اضافی جہتیں شامل کرنے سے وابستہ حجم میں تیزی سے اضافہ ہوتا ہے۔ مثال کے طور پر، 102 = 100 یکساں فاصلہ والے نمونہ نقطے ایک اکائی وقفہ (ایک "1-جہتی مکعب") کے نمونے کے لیے کافی ہیں جس میں نقطوں کے درمیان فاصلہ 10−2 = 0.01 سے زیادہ نہیں ہے۔ 10 جہتی اکائی مکعب کے مساوی نمونے کے لیے ایک جالی جس میں ملحقہ نقطوں کے درمیان فاصلہ 10−2 = 0.01 ہے 1020 = [(102)10] نمونہ نقطوں کی ضرورت ہوگی۔ عام طور پر، 10−n کے فاصلہ کے ساتھ 10-جہتی اکائی مکعب 10n(10−1) = [(10n)10/(10n)] جہتی اکائی مکعب سے "بڑا" ہوتا ہے، جو اکائی کا وقفہ ہے۔ مندرجہ بالا مثال میں n = 2: 0.01 کا نمونہ لینے کا فاصلہ استعمال کرتے وقت 10 جہتی اکائی مکعب کا وقفہ سے 1018 "بڑا" دکھائی دیتا ہے۔ یہ اثر مندرجہ بالا تالیفیات کے مسائل کا مجموعہ ہے اور فاصلاتی کام کے مسائل جو نیچے بیان کیے گئے ہیں۔
اصلاح
[ترمیم]عددی پسماندہ شمولیت کے ذریعے متحرک اصلاح کے مسائل کو حل کرتے وقت، اقدار کے ہر مجموعہ کے لیے افعال کے مقصد کو شمار کیا جانا چاہیے۔ یہ ایک اہم رکاوٹ ہے جب "حالت متغیر" کا طول و عرض بڑا ہوتا ہے۔[3]
مشین آموزی کے مسائل میں جن میں ایک اعلیٰ جہتی خصوصیت والی جگہ میں اعداد و شمار کے نمونوں کی ایک محدود تعداد سے "فطرت کی حالت" سیکھنا شامل ہے جس میں ہر ایک خصوصیت کی ممکنہ اقدار کی ایک حد ہوتی ہے، اس بات کو یقینی بنانے کے لیے عام طور پر بہت زیادہ تربیتی اعداد و شمار کی ضرورت ہوتی ہے کہ اقدار کے ہر ایک مجموعہ کے ساتھ کئی نمونے موجود ہوں۔
انگوٹھے کا ایک عام اصول یہ ہے کہ نمائندگی میں ہر جہت کے لیے کم از کم 5 تربیتی مثالیں ہونی چاہئیں۔[4] مشین آموزی میں اور جہاں تک پیشین گوئی کی کارکردگی کا تعلق ہے، جہت کی لعنت کو چوٹی کے رجحان کے ساتھ ایک دوسرے کے ساتھ استعمال کیا جاتا ہے، [4] جسے ہیوز کا رجحان بھی کہا جاتا ہے۔[5] یہ رجحان بتاتا ہے کہ تربیتی نمونوں کی ایک مقررہ تعداد کے ساتھ، درجہ بندی کرنے والے یا رجعت کرنے والے کی اوسط (متوقع) پیشن گوئی کی طاقت پہلے بڑھ جاتی ہے کیونکہ استعمال شدہ جہتوں یا خصوصیات کی تعداد میں اضافہ ہوتا ہے لیکن ایک خاص جہت سے آگے یہ مسلسل بہتر ہونے کی بجائے بگڑنے لگتا ہے۔[6][7][8]
بہر حال، ایک سادہ درجہ بندی کے تناظر میں زولانواری (ایک عام معلوم ہم آہنگی میٹرکس (ریاضی) کے مفروضے کے تحت متعدد متغیرات کے گاوسی ماڈل میں لکیری امتیازی تجزیہ) [9] نے تجزیاتی اور تجرباتی طور پر ظاہر کیا کہ جب تک ایک اضافی خصوصیات کے مجموعے کی نسبتاً مجموعی افادیت (خصوصیات کے حوالے سے جو پہلے سے درجہ بندی کا حصہ ہیں) سے زیادہ (یا کم) ہے۔ اس اضافی خصوصیات کا حجم، ان اضافی خصوصیات کا استعمال کرتے ہوئے بنائے گئے درجہ بندی کی متوقع غلطی ان کے بغیر بنائے گئے درجہ بندی کی متوقع غلطی سے کم (یا زیادہ) ہوگی۔ دوسرے لفظوں میں، اضافی خصوصیات کا حجم اور ان کا (رشتہ دار) مجموعی امتیازی اثر دونوں اوسط پیشن گوئی کی طاقت میں کمی یا اضافے کے مشاہدے میں اہم ہیں۔
اعداد و شمار کی تجزیہ کاری
[ترمیم]انفرادی نام | وراثہ 1 | وراثہ 2 | ... | وراثہ 2000 |
---|---|---|---|---|
انفرادی 1 | 1 | 0 | ... | 1 |
... | ... | ... | ... | ... |
انفرادی 200 | 0 | 1 | ... | 1 |
اعداد و شمار کی تجزیہ کاری میں، جہت کی لعنت سے مراد بہت زیادہ خصوصیات کے ساتھ اعداد و شمار کا مجموعہ ہے۔
پہلی جدول پر غور کریں، جس میں 1 یا 0 کے ساتھ 200 افراد اور 2000 وراثہ (خصوصیات) کو دکھایا گیا ہے کہ آیا ان میں اس وراثہ میں جینیاتی تبدیلی ہے یا نہیں۔ اس عداد و شمار کا مجموعہ کے لیے اعداد و شمار کی تجزیہ کارکی درخواست مخصوص جینیاتی تغیرات کے درمیان تعلق کو تلاش کر رہی ہے اور درجہ بندی الگورتھم بنا رہی ہے جیسا کہ فیصلہ کرنے والا درخت یہ تعین کرنے کے لیے کہ آیا کسی فرد کو کینسر ہے یا نہیں۔
جوڑوں کی تعداد | ترتیب کے لیے حساب | ہر قطار کے حساب سے ترتیب کی تعداد |
---|---|---|
2 | 3998000 | |
3 | 7988004000 | |
4 | 15952043988000 | |
5 | 31840279800048000 |
اس ساحہ میں اعداد و شمار کی تجزیہ کاری کا ایک عام عمل یہ ہوگا کہ جینیاتی تغیرات کے درمیان تنظیم کے اصول بنائے جائیں جو کینسر کی نشو و نما کا باعث بنتے ہیں۔ ایسا کرنے کے لیے، کسی کو ہر فرد کے جینیاتی تغیرات کو تلاش کرنا ہوگا اور دیگر جینیاتی تغیرات تلاش کرنا ہوں گے جو مطلوبہ حد سے زیادہ ہوتے ہیں اور جوڑے بناتے ہیں۔ وہ دو، پھر تین، پھر چار کے جوڑوں سے شروع کریں گے جب تک کہ ان کے نتیجے میں جوڑوں کا ایک خالی مجموعہ نہ بن جائے۔ اس الگورتھم کی پیچیدگی ہر فرد یا قطار کے لیے وراثہ کے جوڑوں کی تمام ترتیب کو شمار کرنے کا باعث بن سکتی ہے۔ r کے گروپ کے حجم کے ساتھ n اشیاء کی ترتیب کو شمار کرنے کا فارمولہ دیا گیا ہے: کسی بھی فرد کے تین جوڑے کی ترتیب کی تعداد کا حساب لگانا ہر فرد کے لیے وراثہ کے 7988004000 مختلف جوڑے ہوں گے۔ جوڑوں کا حجم بڑھنے کے ساتھ ہی تشکیل شدہ جوڑوں کی تعداد حقیقت پسندانہ کی ترتیب سے بڑھے گی۔ ترقی کو ترتیب جدول میں دکھایا گیا ہے۔
جیسا کہ ہم اوپر کی ترتیب کے جدول سے دیکھ سکتے ہیں، اعداد و شمار کان کنوں کو جہتی کی لعنت کے حوالے سے درپیش اہم مسائل میں سے ایک یہ ہے کہ اعداد و شمار کا مجموعہ میں خصوصیات کی تعداد بڑھنے کے ساتھ ہی ممکنہ اصولوں کی قدروں کی جگہ تیزی سے یا حقیقتی طور پر بڑھتی ہے۔ یہ مسئلہ حسابات وقت اور جگہ دونوں کو تنقیدی طور پر متاثر کرتا ہے جب انجمنوں یا غور کرنے کے لیے بہترین خصوصیات کی تلاش کرتے ہیں۔
بہت زیادہ خصوصیات سے نمٹنے کے دوران اعداد و شمار کے تجزیہ کاروں کو ایک اور مسئلہ درپیش ہو سکتا ہے یہ خیال کہ اعداد و شمار کے مجموعے میں خصوصیات کی تعداد بڑھنے کے ساتھ ہی غلط پیشن گوئیوں یا درجہ بندیوں کی تعداد میں اضافہ ہوتا ہے۔ درجہ بندی کے مسئلے کے حوالے سے جس پر اوپر بحث کی گئی ہے، ہر اعداد و شمار کے نکات کو برقرار رکھنے سے ماڈل میں غلط مثبت اور غلط منفی کی ایک بڑی تعداد ہو سکتی ہے۔
یہ متضاد معلوم ہو سکتا ہے لیکن اوپر سے جینیاتی تغیراتی جدول پر غور کریں، جس میں ہر فرد کے لیے تمام جینیاتی تغیرات کو دکھایا گیا ہے۔ ہر جینیاتی تغیر، چاہے وہ کینسر سے تعلق رکھتا ہو یا نہیں، ماڈل میں کچھ ان پٹ یا وزن ہوگا جو الگورتھم کے فیصلہ سازی کے عمل کی رہنمائی کرتا ہے۔ ایسے اتپریورتن ہو سکتے ہیں جو باہر ہیں یا وہ ہیں جو جینیاتی اتپریورتنوں کی مجموعی تقسیم پر حاوی ہیں جب کہ حقیقت میں ان کا کینسر سے کوئی تعلق نہیں ہے۔ یہ خصوصیات کسی کے ماڈل کے خلاف کام کر سکتی ہیں، جس سے زیادہ سے زیادہ نتائج حاصل کرنا مشکل ہو جاتا ہے۔
بہت زیادہ خصوصیات سے نمٹنے کے دوران اعداد و شمار کے تجزیہ کارو کو ایک اور مسئلہ درپیش ہو سکتا ہے یہ خیال کہ اعداد وشمار میں خصوصیات کی تعداد بڑھنے کے ساتھ ہی غلط پیشین گوئیوں یا درجہ بندیوں کی تعداد میں اضافہ ہوتا ہے۔ درجہ بندی کے مسئلے کے حوالے سے جس پر اوپر بحث کی گئی ہے، ہر اعداد و شمار کے نکات کو برقرار رکھنے سے ماڈل میں غلط مثبت اور غلط منفی کی ایک بڑی تعداد ہو سکتی ہے۔جیسا کہ ہم اوپر کی ترتیب کے جدول سے دیکھ سکتے ہیں، اعداد و شمار کے کو جہتی کی لعنت کے حوالے سے درپیش اہم مسائل میں سے ایک یہ ہے کہ اعداد و شمار کے مجموعے میں خصوصیات کی تعداد بڑھنے کے ساتھ ہی ممکنہ نکات کی قدروں کی جگہ تیزی سے یا حقیقتی طور پر بڑھتی ہے۔
ترقی کو ترتیب جدول میں دکھایا گیا ہے۔
حوالہ جات
[ترمیم]- ↑ Richard Ernest Bellman، Rand Corporation (1957)۔ Dynamic programming۔ Princeton University Press۔ صفحہ: ix۔ ISBN 978-0-691-07951-6,
Republished: Richard Ernest Bellman (2003)۔ Dynamic Programming۔ Courier Dover Publications۔ ISBN 978-0-486-42809-3 - ↑ Richard Ernest Bellman (1961)۔ Adaptive control processes: a guided tour۔ Princeton University Press۔ ISBN 9780691079011
- ↑ C. Robert Taylor (1993)۔ "Dynamic Programming and the Curses of Dimensionality"۔ Applications Of Dynamic Programming To Agricultural Decision Problems۔ Westview Press۔ صفحہ: 1–10۔ ISBN 0-8133-8641-1
- ^ ا ب Konstantinos Koutroumbas، Sergios Theodoridis (2008)۔ Pattern Recognition (4th ایڈیشن)۔ Burlington۔ ISBN 978-1-59749-272-0۔ اخذ شدہ بتاریخ 08 جنوری 2018
- ↑ G.F. Hughes (January 1968)۔ "On the mean accuracy of statistical pattern recognizers"۔ IEEE Transactions on Information Theory۔ 14 (1): 55–63۔ doi:10.1109/TIT.1968.1054102
- ↑ G. V. Trunk (July 1979)۔ "A Problem of Dimensionality: A Simple Example"۔ IEEE Transactions on Pattern Analysis and Machine Intelligence۔ PAMI-1 (3): 306–307۔ PMID 21868861۔ doi:10.1109/TPAMI.1979.4766926
- ↑ B. Chandrasekaran، A. K. Jain (1974)۔ "Quantization Complexity and Independent Measurements"۔ IEEE Transactions on Computers۔ 23 (8): 102–106۔ doi:10.1109/T-C.1974.223789
- ↑ G. J. McLachlan (2004)۔ Discriminant Analysis and Statistical Pattern Recognition۔ Wiley Interscience۔ ISBN 978-0-471-69115-0۔ MR 1190469
- ↑ A. Zollanvari، A. P. James، R. Sameni (2020)۔ "A Theoretical Analysis of the Peaking Phenomenon in Classification"۔ Journal of Classification۔ 37 (2): 421–434۔ doi:10.1007/s00357-019-09327-3